package com.xyhuo.leetcode.december;

import java.util.Arrays;

/**
 * 下一个排列
 * https://leetcode.cn/problems/next-permutation/
 *
 * @time 2023/12/12
 */
public class NextPermutation {

//    public static void main(String[] args) {
//        NextPermutation np = new NextPermutation();
//        int[] nums = {4, 2, 0, 2, 3, 2, 0};
//        np.nextPermutation(nums);
//        System.out.println(nums);
//    }

    public void nextPermutation(int[] nums) {
        int len = nums.length;
        int left = -1, right = -1;
        for (int i = len - 1; i > 0; i--) {
            int index = i - 1;
            //剪枝
            if (index < left) {
                break;
            }
            while (index >= 0) {
                if (nums[index] < nums[i]) {
                    if (index > left) {
                        left = index;
                        right = i;
                    }
                }
                index--;
            }
        }
        if (left != -1) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            Arrays.sort(nums, left + 1, len);
        } else {
            Arrays.sort(nums);
        }

    }
}
